Corelab Seminar
2016-2017
Platonas Papadopoulos
Advances in Circuit Lower Bounds
Abstract.
Non-Uniform Complexity is a very well-studied computational setting with various connections to Complexity Theory, and especially to lower bounds for uniform complexity classes. More precisely, exponential circuit lower bounds for hard functions would imply the existence of algorithms that achieve effective derandomization (thus BPP=P), whilst the existence of polynomial circuits would imply the seperation of P from NP. However, Rasborov and Rudich's natural proofs paper had for almost two decades removed hope from the research community that an easy proof for P vs NP (and similar separation results) would arise from a circuit lower bound argument.
In this introductory talk, we present, among others, some recent innovative ideas by R. Williams, utilizing algorithmic ideas in circuit analysis, which culminate into new lower bounds for uniform classes and thus propose a fresh framework in that direction.